package org.example.myleet.p1190;

import java.util.*;

/**
 * O(2n)方案，预处理括号，然后在遇到括号的时候跳跃到对应的另一边括号并反方向前进
 * 2 ms，数据量不够多，体现不出低时间复杂度的优势
 */
public class Solution1 {
    public String reverseParentheses(String s) {
        int i = 0, len = s.length();
        Map<Integer, Integer> jumpPoint = new HashMap<>();
        Deque<Integer> stack = new LinkedList<>();
        //利用栈预处理括号对，对应括号的跳跃点记录在jumpPoint的Map中
        while (i < len) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(i);
            } else if (c == ')') {
                Integer left = stack.pop();
                jumpPoint.put(left, i);
                jumpPoint.put(i, left);
            }
            ++i;
        }
        i = 0;
        //true是向右前进，false是向左前进
        boolean forward = true;
        int ti = 0;
        char[] target = new char[len];
        while (i < len) {
            char c = s.charAt(i);
            if (c == '(' || c == ')') {
                //遇到括号就跳跃游标，并将前进方向取反
                i = jumpPoint.get(i);
                forward = !forward;
            } else {
                //遇到字母就拼接
                target[ti++] = c;
            }
            if (forward) {
                //向右前进
                ++i;
            } else {
                //向左前进
                --i;
            }
        }
        return new String(Arrays.copyOf(target, ti));
    }
}
